package leetCode.sample;


/**
 * 字符串相乘
 * https://leetcode-cn.com/problems/multiply-strings/
 *
 * @author zhangzhiping
 * @date 7:42 下午 2020/7/8
 */
public class MultiStringSolution {

    public static void main(String[] args) {
        MultiStringSolution obj = new MultiStringSolution();
        //System.out.println(obj.multiply1("30", "2"));
        // System.out.println(obj.multiply1("33", "5"));
        System.out.println(obj.multiply1("123", "456"));
        System.out.println(obj.multiply2("123", "456"));
    }

    public String multiply2(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        StringBuilder result = new StringBuilder();
        int[] res = new int[num1.length() + num2.length()];
        for (int i1 = num1.length() - 1; i1 >= 0; i1--) {
            int n1 = num1.charAt(i1) - '0';
            for (int i2 = num2.length() - 1; i2 >= 0; i2--) {
                int n2 = num2.charAt(i2) - '0';
                int tmp = res[i1 + i2 + 1] + n1 * n2;
                res[i1 + i2 + 1] = tmp % 10;
                res[i1 + i2] += tmp / 10;
            }
        }
        boolean isHead = true;
        for (int i = 0; i < res.length; i++) {
            if (isHead && res[i] == 0) {
                continue;
            }
            isHead = false;
            result.append(res[i]);
        }
        return result.toString();
    }


    public String multiply1(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        String result = "";
        StringBuilder base = new StringBuilder("");
        int i2 = num2.length() - 1;
        while (i2 >= 0) {
            int j = num2.charAt(i2) - '0';
            int i1 = num1.length() - 1;
            String tmp = "";
            int dz = 0;
            while (i1 >= 0) {
                int i = num1.charAt(i1) - '0';
                int r = i * j + dz;
                tmp = r % 10 + tmp;
                dz = r / 10;
                i1--;
            }
            if (dz > 0) {
                tmp = dz + tmp;
            }
            tmp = tmp + base;
            result = addStrings(result, tmp);
            i2--;
            base.append("0");
        }
        return result;
    }


    public static String addStrings(String num1, String num2) {
        if (num1 == null || num1.isEmpty()) {
            return num2;
        }
        if (num2 == null || num2.isEmpty()) {
            return num1;
        }
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        StringBuilder result = new StringBuilder("");
        int dz = 0;
        while (n1 >= 0 || n2 >= 0) {
            int c1 = n1 >= 0 ? num1.charAt(n1) - '0' : 0;
            int c2 = n2 >= 0 ? num2.charAt(n2) - '0' : 0;
            int sum = c1 + c2 + dz;
            result.insert(0, sum % 10);
            dz = sum / 10;
            n1--;
            n2--;
        }
        if (dz != 0) {
            result.insert(0, 1);
        }
        return result.toString();
    }
}
